package LeetCodeQuestionBank;
/**
 * 给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 *
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 *
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 *
 *
 * 提示：
 *
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 *
 *
 * 进阶：你能尝试使用一趟扫描实现吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 */
public class T019 {
    /**
     *
     *解题思路：1 使用快慢指针 让快指针 先走n步 ，然后快慢指针一起走 当快指针走到结尾时 慢指针的位置就是倒数第n个节点
     * 2 使用连个栈  进行操作
     * 3 先遍历一次 确定节点数量 再确定倒数第N个节点的位置
     *
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        //定义快慢指针
        ListNode fast = head;
        ListNode dump = new ListNode(0, head);
        ListNode slow = dump; //指针直指节点自己时 不好删除自己 可以在头节点加一个节点 通过前驱节点可以方便的删除后一个节点


        //先让快指针走 n个节点 第一个是倒数第 n个节点 所以要从1开始算起
        for (int i = 1; i < n; i++) {
            fast = fast.next;
        }


        //两个指针一起走 直到快指针走到结尾
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        //开始删除
        slow.next = slow.next.next;


        return dump.next;

    }

    //链表的定义
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        T019 t019 = new T019();
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
//        ListNode l3= new ListNode(3);
//        ListNode l4= new ListNode(4);
//        ListNode l5= new ListNode(5);

        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
//        l4.next = l5;

        ListNode listNode = t019.removeNthFromEnd(l1, 2);

    }
}
